Networks of computer systems are ubiquitous in our society and such networks range in size from two-computer local area networks to wide area networks which include thousands of computers and which span the entire world. It is frequently desirable to send a message to many other computers of a computer network.
Multicasting is a mechanism by which a relatively low number of messages can be used to convey a message to many computers of a computer network. Consider, for example, computer network 100 shown in FIG. 1. Suppose computer 102A has a message to send to all computers 102B-CC of computer network 100. Through multicast, computer 102A forms a single copy of the message and sends the message to computers 102B-D to which computer 102A is directly coupled through computer network 100 as shown. Computer 102D recognizes the message as multicast and forms additional copies to send to computers 102E-H, to which computer 102D is directly coupled through computer network 102D as shown. Similarly, computer 102H forwards copies of the message to computers 102J-L, and the message is propagated through computer network 100 to all of computers 102B-CC.
Unicast is a messaging protocol in which each message has an intended recipient. Using unicast to send a message from computer 102A to computers 102B-CC involves twenty-six separate messages transmitted through the portion of computer network 100 between computers 102A and 102D. By comparison, multicast transmits a single message through the same portion of computer network 100. The efficiency of multicast relative to unicast is relatively modest in this illustrative example in comparison to multicast messages through wide-area networks which include thousands of computers.
It is frequently desirable to send messages to a local portion of a wide-area network. Messages therefore include a time-to-live (TTL) parameter which establishes a condition for expiration of a multicast message. The TTL parameter of a multicast message is initialized by the sending computer and is decreased by each computer which forwards the multicast message. In some networks, the TTL parameter of a multicast message is decremented, i.e., decreased by one, by each computer which forwards the message such that the TTL parameter specifies an expiration condition in terms of network hops. In other networks, each computer which forwards a message decreases the TTL parameter of the message by an amount of time required to transfer the message to the computer such that the TTL parameter specifies an expiration condition in terms of an amount of time the message is permitted to travel. Some of the latter networks require that each computer decrease the TTL parameter by at least one second such that the TTL parameter specifies an expiration condition in terms of a combination of a maximum number of network hops and a maximum amount of time. When the TTL parameter of a multicast message is decreased below a predetermined threshold, which is typically zero, the multicast message is destroyed. The following example is illustrative.
Suppose computer 102A wishes to send a multicast message to computers 102B-G. Computer 102A can form a multicast message with a TTL parameter whose value is two. The message reaches computers 102B-D since computers 102B-D are coupled directly to computer 102A through computer network 100. Computer 102D decrements the TTL parameter of the message to have a value of one and forwards the multicast message to computers 102E-H. Thus, computers 102B-G receive the multicast message. In addition, computer 102H receives the multicast message. Computer 102H decrements the TTL parameter of the multicast message to have a value of zero. Accordingly, computer 102H destroys the multicast message. As a result, the multicast message does not pass beyond computer 102H and does not unnecessarily burden the remainder of computer network 100.
It is sometimes desirable to send a message to a subset of a computer network in which most of the nodes of the subset are relatively close to the node sending the message and a few are relatively far from the sending node. In such situations, multicast messages reach too far into the computer network such that nodes which do not need to receive the message nonetheless do and must also route the message. Accordingly, unintended recipients of the message have more message traffic than necessary. Conversely, unicast messages have the above-described inefficiencies with respect to message redundancy for relatively close recipient nodes.
Consider, for example, a message which computer 102A sends to computers 102B-G and 102X. Sending the message as a unicast message involves sending seven nearly identical messages through the portion of computer network 100 between computers 102A-D. Such is a relatively significant burden upon that portion of computer network 100. Sending the message as a multicast message involves sending a multicast message with a TTL parameter whose value is sufficiently large to reach the furthest intended recipient node, i.e., computer 102X in this illustrative example. Such reduces the amount of traffic between computers 102A-D since a single message is sent through that portion of computer network 100. However, the multicast message reaches significantly beyond computer 102X. In this illustrative example, the multicast message reaches all of computers 102B-CC since all of computers 102B-CC can be reached by a multicast message with a TTL parameter sufficiently large that the message can reach computer 102X. Accordingly, computers 102M-Q and 102Z-CC receive the multicast message unnecessarily since none of those computers connect computer 102A to any recipient computer.
What is needed is a mechanism by which computers of a computer network can efficiently distribute messages to other computers of the computer network without requiring excessive message traffic throughout the computer network.